{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 32.3 String matching with finite automata"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.3-1\n",
    "\n",
    "> Construct the string-matching automaton for the pattern $P = aabab$ and illustrate its operation on the text string $T = aaababaabaababaab$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./img/32.3-1_1.png)\n",
    "\n",
    "$0 \\rightarrow 1 \\rightarrow 2 \\rightarrow 2 \\rightarrow 3 \\rightarrow 4 \\rightarrow 5$ $\\rightarrow$ $1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 4 \\rightarrow 2 \\rightarrow 3 \\rightarrow 4 \\rightarrow 5$ $\\rightarrow$ $1 \\rightarrow 2 \\rightarrow 3$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.3-2\n",
    "\n",
    "> Draw a state-transition diagram for a string-matching automaton for the pattern\n",
    "$ababbabbababbababbabb$ over the alphabet $\\sigma = \\{a, b\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| State | a | b |\n",
    "|:-----:|:-:|:-:|\n",
    "|   0   | 1 | 0 |\n",
    "|   1   | 1 | 2 |\n",
    "|   2   | 3 | 0 |\n",
    "|   3   | 1 | 4 |\n",
    "|   4   | 3 | 5 |\n",
    "|   5   | 6 | 0 |\n",
    "|   6   | 1 | 7 |\n",
    "|   7   | 3 | 8 |\n",
    "|   8   | 9 | 0 |\n",
    "|   9   | 1 |10 |\n",
    "|  10   |11 | 0 |\n",
    "|  11   | 1 |12 |\n",
    "|  12   | 3 |13 |\n",
    "|  13   |14 | 0 |\n",
    "|  14   | 1 |15 |\n",
    "|  15   |16 | 8 |\n",
    "|  16   | 1 |17 |\n",
    "|  17   | 3 |18 |\n",
    "|  18   |19 | 0 |\n",
    "|  19   | 1 |20 |\n",
    "|  20   | 3 |21 |\n",
    "|  21   | 9 | 0 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.3-3\n",
    "\n",
    "> We call a pattern $P$ __*nonoverlappable*__ if $P_k \\sqsupset P_q$ implies $k = 0$ or $k = q$. Describe the state-transition diagram of the string-matching automaton for a nonoverlappable pattern."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\delta(q, a) \\in \\{q+1, 0\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.3-4 $\\star$\n",
    "\n",
    "> Given two patterns $P$ and $P'$, describe how to construct a finite automaton that determines all occurrences of either pattern. Try to minimize the number of states in your automaton."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Combine the common prefix and suffix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.3-5\n",
    "\n",
    "> Given a pattern $P$ containing gap characters (see Exercise 32.1-4), show how to build a finite automaton that can find an occurrence of $P$ in a text $T$ in $O(n)$ matching time, where $n = |T|$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Split the string with the gap characters, build finite automatons for each substring. When a substring is matched, moved to the next finite automaton."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
